package com.leetcode.partition7;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/8/16 10:11
 */
public class LC637二叉树的层平均值 {

    public static List<Double> averageOfLevels(TreeNode root) {
        return bfs(root);
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(20), new TreeNode(7)));
        System.out.println(averageOfLevels(n1));
    }

    private static List<Double> bfs(TreeNode root) {
        List<Double> answer = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            double sum = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.pollFirst();
                sum += cur.val;
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
            }
            answer.add(sum / size);
        }

        return answer;
    }
}
